Motivation Sometime ago, just like everyone else, I managed to get addicted to the 2048 game. Whenever, I wanted to take a break from work, I would just open up a new tab and begin the repetitious arrow smashing. Watching the tiles fly by was just as much fun as actually trying to mine for that prized 2048 tile. Unfortunately, the game wouldn't just complete in minutes and I saw myself consistently spending more time on this game than I should. From an academic perspective, I thought it would be interesting to build an artificial intelligence (AI) to play the game for me. I reasoned that if I could get something to play for me, then I invariably have solved the game and would no longer be inclined to play it anymore and waste my time. I was definitely wrong. Now that I have an AI playing the game for me, I tend to waste time not playing the game but by simply sitting there and watching the tiles move about, waiting for notable errors in my heuristic. Artificial Intelligence Explanation On every turn, the artificial intelligence is essentially making all 4 moves: UP, DOWN, LEFT, RIGHT and evaluating which one would be the best decision based on which one brings it closer to winning. Since the game is randomized and at every step a random block is generated, the AI algorithm also generated all possible tiles in the available empty tiles with values of 2 and 4. It then continues to make moves and attempts to account for all possible random tile generations. Because the AI is able to consider all possible future moves, shouldn't it always be able to win?Unfortunately, because considering all those cases grows exponentially and our browsers have limited CPU bandwidth, the algorithm above only looks 6 moves into the future. Check out the Time Calculations section for an analysis of the algorithm's speed. So after looking 6 moves into the future, it uses a heuristic to estimate the value of the moves that has made. After evaluating all possible moves, it chooses the one that achieves the highest estimated value according to the heuristic. Artificial Intelligence Algorithm My two main requirements for the AI was to always win the game (achieve the 2048 tile) and to be fast enough to be rendered seamlessly using client side javascript. The algorithm I used is expectimax. It follows the following recurrence relationship:  where state encodes the current game state with the location and values of all the tiles. Utility(state) is described in the Heuristics section below. PLAYER is an identifier indicating that it is the player's turn to move. After every turn, the BOARD generates a random tile. Prob(state, tile) is the probability of a given tile with a specific location and value showing up on given state described by state. For a given location the probability of a tile with a value of 2 occurring is 0.9 while a value of 4 occurring is 0.1. Successor(state, a) returns the state of the game after applying action a on the state. Finally, GenerateTIle() adds the tile to the state and returns the new state of the game. Heuristics I used three separate heuristics to evaluate the utility of a given game state. Empty Tiles The first heuristic was rather simple. It main main was to maximize the number of empty tiles on the board. However, every turn, the board generates a new tile. The intuition behind this heuristic was that the only way to move towards a board with more empty tiles is by merging blocks together. Merging blocks aligned perfectly with the main objective of the game and the heuristic performed rather well. Monotonicity  The next heuristic attempted to maximize monotonicity on the grid. In other words, in the 4 directions, up, down, left and right, the heuristic attempted to arrange the numbers in decreasing order along one of those 4 directions. Gradients  The final heuristic assigned a varying weight to each of the different tiles in the board. Tiles in the corner were assigned a high weight to optimize for either one of the four corners. The heuristic pushed the highest valued tiles to one of the corners. This also increased the surface area of smaller valued tiles to occur next to the newly generated tiles, allowing easy merging without much reordering. Results The results for the three heuristics are shown in the table here. The gradient outperforms the other heuristics and is the one that is used in the AI above.
Comparisons to Minimax I also implemented a Minimax algorithm and the source for that can also be found in the repository. Unlike the expectimax algorithm, minimax optimizes for the worse case generation of tiles. It assumes that the board is not randomly generating tiles but is doing so to prevent the user from winning. The recurrence relationship that my minimax follows is below:  where the methods are the same as the ones described above for expectimax. Unfortunately, the assumption minimax makes performs a lot worse than expectimax. In an attempt to prevent a losing scenario, it fails to take risks and merge the medium sized tiles of value 8 or 16, essentially causing the algorithm to lose more often than it should. However, if this algorithm wasn't being optimized for rendering the animation, and was implemented on a server, it would be able to search to a higher depth, allowing the algorithm to perform a lot better. Time Calculations One of the biggest bottle necks of this algorithm is not being able to render the animation for the game and still have an efficient AI play the game using client side javascript. To that end, I conducted the following benchmarks for run time of the AI algorithms I implemented.
The current algorithm used above uses expectimax with a depth of 6 that varies if the number of empty tile is higher than a given threshold. It assumes that each move takes approximately 450ms to complete along with the animations in order to generate a smooth viewing of the AI in action. Main Takeaway I had a lot of fun implementing this. There are tons of improvements and benchmarks to run but I don't have the time to spend on this. Hope you enjoy this game as much as I have and like watching the AI "do it's thing".
19 Comments
|
RSS Feed